package nachos.threads;

import java.util.Comparator;
import nachos.machine.*;

import java.util.TreeSet;

import java.util.Iterator;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {
    /**
     * Allocate a new priority scheduler.
     */
    public PriorityScheduler() {
    }

    /**
     * Allocate a new priority thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer priority from waiting threads
     *					to the owning thread.
     * @return	a new priority thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
	return new PriorityQueue(transferPriority);
    }

    public int getPriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());

	return getThreadState(thread).getPriority();
    }

    public int getEffectivePriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());

	return getThreadState(thread).getEffectivePriority();
    }

    public void setPriority(KThread thread, int priority) {
	Lib.assertTrue(Machine.interrupt().disabled());

	Lib.assertTrue(priority >= priorityMinimum &&
		   priority <= priorityMaximum);

	getThreadState(thread).setPriority(priority);
    }

    public boolean increasePriority() {
	boolean intStatus = Machine.interrupt().disable();

	KThread thread = KThread.currentThread();

	int priority = getPriority(thread);
	if (priority == priorityMaximum)
	    return false;

	setPriority(thread, priority+1);

	Machine.interrupt().restore(intStatus);
	return true;
    }

    public boolean decreasePriority() {
	boolean intStatus = Machine.interrupt().disable();

	KThread thread = KThread.currentThread();

	int priority = getPriority(thread);
	if (priority == priorityMinimum)
	    return false;

	setPriority(thread, priority-1);

	Machine.interrupt().restore(intStatus);
	return true;
    }

    /**
     * The default priority for a new thread. Do not change this value.
     */
    public static final int priorityDefault = 1;
    /**
     * The minimum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMinimum = 0;
    /**
     * The maximum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMaximum = 7;

    /**
     * Return the scheduling state of the specified thread.
     *
     * @param	thread	the thread whose scheduling state to return.
     * @return	the scheduling state of the specified thread.
     */
    protected ThreadState getThreadState(KThread thread) {
	if (thread.schedulingState == null)
	    thread.schedulingState = new ThreadState(thread);

	return (ThreadState) thread.schedulingState;
    }

     /**
     * A <tt>Priority Comparator</tt> to sort the PriorityQueue
     */

    protected class PriorityComparator implements Comparator<KThread>{
       final static boolean FORCE_EFFECTIVE = true;

     /**
     * Allocate a new priority comparator.
     *
     * @param	transferPriority	<tt>true</tt> if this comparator should
     *					should compare for transfer priority.
     * @return	a new priority comparator.
     */
        public PriorityComparator( boolean transferPriority){
            this.transferPriority = transferPriority;
        }
        public int compare(KThread a, KThread b){
            ThreadState tStateA = getThreadState(a);
            ThreadState tStateB = getThreadState(b);
            int compare = 0;
            /*
             * We will asume that the effective priority is at least as equal to
             * normal priority (always).
             */
            int priorityA  =  tStateA.getEffectivePriority();
            int priorityB  =  tStateB.getEffectivePriority();
            
            if(priorityA < priorityB)
                compare = -1;
            else if (priorityA > priorityB)
                compare = 1;
            /* below we asume that the queue in wich the thread belongs is the
             * same in wich the comparator is working.
             */
            else if(tStateA.queue != null && tStateB.queue == null)
                compare = 1;
            else if (tStateB.queue !=null && tStateA.queue == null)
                compare = -1;
            else
                compare = a.compareTo(b);
            
            return compare;
        }

        private boolean transferPriority;
    }
     /**
     * A <tt>ThreadQueue</tt> that sorts threads by priority.
     */
    protected class PriorityQueue extends ThreadQueue{

        

	PriorityQueue(boolean transferPriority) {
	    this.transferPriority = transferPriority;
            this.queue = new TreeSet<KThread>(new PriorityComparator(this.transferPriority));
	}

	public void waitForAccess(KThread thread) {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    getThreadState(thread).waitForAccess(this);
	}

	public void acquire(KThread thread) {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    getThreadState(thread).acquire(this);
	}

	public KThread nextThread() {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    // implement me!!
            KThread thread;
             
            thread = this.queue.pollLast();
            if(this.transferPriority && this.resourceHolder != null){
                getThreadState(this.resourceHolder).resetEffectivePriority();
             }
            if(thread != null)
                getThreadState(thread).queue = null;
            this.resourceHolder = thread;
	    return thread;

	}

	/**
	 * Return the next thread that <tt>nextThread()</tt> would return,
	 * without modifying the state of this queue.
	 *
	 * @return	the next thread that <tt>nextThread()</tt> would
	 *		return.
	 */
	protected ThreadState pickNextThread() {
	    // implement me !!
	    return  getThreadState(this.queue.last());
	}

	public void print() {
	    Lib.assertTrue(Machine.interrupt().disabled());
             for (Iterator i=queue.iterator(); i.hasNext(); )
		System.out.print((KThread) i.next() + " ");
	    // implement me (if you want)
	}

	/**
	 * <tt>true</tt> if this queue should transfer priority from waiting
	 * threads to the owning thread.
	 */
        
	public boolean transferPriority;
        /**
         * The queue that holds the threads, in this case an implementation of a
         * sortedSet.
         */
        protected TreeSet<KThread> queue = new TreeSet<KThread>(
            new PriorityComparator(this.transferPriority)
        );
        /**
         * The thread who are supposed to be the next or actual holder of the
         * resource this queue manages.
         */
        protected KThread resourceHolder = null;

    }

    /**
     * The scheduling state of a thread. This should include the thread's
     * priority, its effective priority, any objects it owns, and the queue
     * it's waiting for, if any.
     *
     * @see	nachos.threads.KThread#schedulingState
     */
    protected class ThreadState {
	/**
	 * Allocate a new <tt>ThreadState</tt> object and associate it with the
	 * specified thread.
	 *
	 * @param	thread	the thread this state belongs to.
	 */
	public ThreadState(KThread thread) {
	    this.thread = thread;

	    setPriority(priorityDefault);
            

	}

	/**
	 * Return the priority of the associated thread.
	 *
	 * @return	the priority of the associated thread.
	 */
	public int getPriority() {
	    return priority;
	}

	/**
	 * Return the effective priority of the associated thread.
	 *
	 * @return	the effective priority of the associated thread.
	 */
	public int getEffectivePriority() {
	    // implement me !!
	    return this.effectivePriority;
	}
        protected void setEffectivePriority(ThreadState donator){

            if (this.effectivePriority >= donator.priority)
		return;
	    this.effectivePriority = donator.priority;
            try{
                PriorityQueue workQueue = (PriorityQueue)this.queue;
                workQueue.queue.remove(this.thread);
                workQueue.queue.add(this.thread);
            }catch(Exception e){
                
                //nothing
            }
        }

	/**
	 * Set the priority of the associated thread to the specified value.
	 *
	 * @param	priority	the new priority.
	 */
	public void setPriority(int priority) {
	    if (this.priority == priority)
		return;

	    this.priority = priority;
	    if (this.effectivePriority < this.priority)
                this.effectivePriority = this.priority;
            
            try{
                PriorityQueue workQueue = (PriorityQueue)this.queue;
                workQueue.queue.remove(this.thread);
                workQueue.queue.add(this.thread);
            }catch(Exception e){
                //nothing
            }
            
	    // implement me !!
	}

	/**
	 * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
	 * the associated thread) is invoked on the specified priority queue.
	 * The associated thread is therefore waiting for access to the
	 * resource guarded by <tt>waitQueue</tt>. This method is only called
	 * if the associated thread cannot immediately obtain access.
	 *
	 * @param	waitQueue	the queue that the associated thread is
	 *				now waiting on.
	 *
	 * @see	nachos.threads.ThreadQueue#waitForAccess
	 */
	public void waitForAccess(PriorityQueue waitQueue) {

            if (waitQueue.transferPriority && waitQueue.resourceHolder != null){
                ThreadState holder = getThreadState(waitQueue.resourceHolder);
                 if(this.priority > holder.getPriority()){
                      holder.setEffectivePriority(this);
                 }
            }
            this.queue = waitQueue;
            waitQueue.queue.add(this.thread);
            // implement me!!

	}

	/**
	 * Called when the associated thread has acquired access to whatever is
	 * guarded by <tt>waitQueue</tt>. This can occur either as a result of
	 * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
	 * <tt>thread</tt> is the associated thread), or as a result of
	 * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
	 *
	 * @see	nachos.threads.ThreadQueue#acquire
	 * @see	nachos.threads.ThreadQueue#nextThread
	 */
	public void acquire(PriorityQueue waitQueue) {
            if(waitQueue.transferPriority && waitQueue.resourceHolder != null){
                getThreadState(waitQueue.resourceHolder).resetEffectivePriority();
            }
            waitQueue.resourceHolder = this.thread;
	    // implement me !!
	}
        public void resetEffectivePriority(){
            this.effectivePriority = this.priority;
            try{
                ((PriorityQueue)this.queue).queue.remove(this.thread);
                ((PriorityQueue)this.queue).queue.add(this.thread);
            }catch(Exception e){
                //do nothing
            }


        }

	/** The thread with which this object is associated. */
	protected KThread thread;
	/** The priority of the associated thread. */
	protected int priority;
        /** The effective priority of the associated thread. */
        protected int effectivePriority = priority;
        /** The queue to wich the thread asociated belongs */
        protected ThreadQueue queue;
    }
}
